package com.lun.other.sort;


/**
 * 
 * 计数排序
 * 
 * from《剑指Offer-专项突破版》何海涛著
 * 
 * @author Jallen
 *
 */
public class Count extends SortingAlgorithm{

	@Override
	public void sort(int[] nums) {
		int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
		
		for(int num : nums) {
			min = Math.min(min, num);
			max = Math.max(max, num);
		}

		int[] counts = new int[max - min + 1];
		
		for(int num : nums) {
			counts[num - min]++;
		}
		
		for(int i = 0, j = 0; j < counts.length; j++) {
			while(counts[j]-- > 0) {
				nums[i++] = j + min;
			}
		}
	}

}
